504,旋转数组的3种解决方式
There are many things that seem impossible only so long as one does not attempt them.
很多事情看起来不可能只是因为没有人尝试过。
问题描述
给定一个数组,将数组中的元素向右移动k
个位置,其中k
是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入:nums = [-1,-100,3,99], k = 2
输出:[3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
提示:
1<=nums.length<=2*10^4
-2^31<=nums[i]<=2^31-1
0<=k<=10^5
使用临时数组解决
这题是让把数组中的每个元素都往右移动k位。最简单的一种解决方式就是使用一个临时数组解决,先把原数组的值存放到一个临时数组中,然后再把临时数组的值重新赋给原数组,重新赋值的时候要保证每个元素都要往后移k位,如果超过数组的长度就从头开始,所以这里可以使用(i + k) % length来计算重新赋值的元素下标
1public void rotate(int nums[], int k) {
2 int length = nums.length;
3 int temp[] = new int[length];
4 // 把原数组值放到一个临时数组中,
5 for (int i = 0; i < length; i++) {
6 temp[i] = nums[i];
7 }
8 // 然后在把临时数组的值重新放到原数组,
9 // 并且往右移动k位
10 for (int i = 0; i < length; i++) {
11 nums[(i + k) % length] = temp[i];
12 }
13}
部分元素多次反转
还有一种方式就是先反转全部数组,在反转前k个,最后在反转剩余的,如下所示
1public void rotate(int[] nums, int k) {
2 int length = nums.length;
3 k %= length;
4 //先反转全部的元素
5 reverse(nums, 0, length - 1);
6 //在反转前k个元素
7 reverse(nums, 0, k - 1);
8 //接着反转剩余的
9 reverse(nums, k, length - 1);
10}
11
12//把数组中从[start,end]之间的元素两两交换,也就是反转
13public void reverse(int[] nums, int start, int end) {
14 while (start < end) {
15 int temp = nums[start];
16 nums[start++] = nums[end];
17 nums[end--] = temp;
18 }
19}
其实还可以在调整下,先反转前面的,接着反转后面的k个,最后在反转全部,原理都一样
1public void rotate(int[] nums, int k) {
2 int length = nums.length;
3 k %= length;
4 //先反转前面的
5 reverse(nums, 0, length - k - 1);
6 //接着反转后面k个
7 reverse(nums, length - k, length - 1);
8 //最后在反转全部的元素
9 reverse(nums, 0, length - 1);
10}
11
12//把数组中从[start,end]之间的元素两两交换,也就是反转
13public void reverse(int[] nums, int start, int end) {
14 while (start < end) {
15 int temp = nums[start];
16 nums[start++] = nums[end];
17 nums[end--] = temp;
18 }
19}
环形旋转
类似约瑟夫环一样,把数组看作是环形的,每一个都往后移动k位,这个很好理解,画个图来看一下
但这里有一个坑,如果nums.length%k=0
,也就是数组长度为k的倍数,这个会原地打转,如下图所示
对于这个问题我们可以使用一个数组visited表示这个元素有没有被访问过,如果被访问过就从他的下一个开始,防止原地打转。
1public static void rotate(int[] nums, int k) {
2 int hold = nums[0];
3 int index = 0;
4 int length = nums.length;
5 boolean[] visited = new boolean[length];
6 for (int i = 0; i < length; i++) {
7 index = (index + k) % length;
8 if (visited[index]) {
9 //如果访问过,再次访问的话,会出现原地打转的现象,
10 //不能再访问当前元素了,我们直接从他的下一个元素开始
11 index = (index + 1) % length;
12 hold = nums[index];
13 i--;
14 } else {
15 //把当前值保存在下一个位置,保存之前要把下一个位置的
16 //值给记录下来
17 visited[index] = true;
18 int temp = nums[index];
19 nums[index] = hold;
20 hold = temp;
21 }
22 }
23}
总结
这题使用前两种方式是最容易想到的,也是比较简单的,第3种方式也容易想到,但操作起来可能稍微有点难度。
截止到目前我已经写了500多道算法题了,为了方便大家阅读,我把部分算法题整理成了pdf文档,目前有800多页,大家可以在公众号中回复关键字“pdf”即可获取下载链接。
如果觉得有用就点个"赞"吧